package SuanFa.AtGuiGu;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class StringSuanfa {


    public static void main(String[] args) {
        StringSuanfa ssf = new StringSuanfa();
        Boolean b = ssf.repeatedSubstringPattern("abcabcabcabc");
        System.out.println(b);
        System.out.println("-------------获取一个字符串在另一个字符串中出现的次数---------------");
        String s1 = "abkkcadkabkebfkabkskab";
        String s2 = "abababababababababababab";
        int num1 = ssf.times(s2, "ab");
        System.out.println(num1);

        //    5.对字符串中字符进行自然顺序排序。
        String s3 = "wersdfgaeragsdgv";
        char[] c1 = s1.toCharArray();
        Arrays.sort(c1);
        String s4 = new String(c1);
        System.out.println(s2);
    }

//    3、重复的子字符串
//    给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。
//    示例 1:
//    输入: "abab"
//    输出: True
//    解释: 可由子字符串 "ab" 重复两次构成。
//    示例 2:
//    输入: "aba"
//    输出: False
//    示例 3:
//    输入: "abcabcabcabc"
//    输出: True
//    解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)

    public boolean repeatedSubstringPattern(String s) {
        int n = s.length();
        for (int i = 1; i * 2 <= n; ++i) {
            if (n % i == 0) {
                boolean match = true;
                for (int j = i; j < n; ++j) {
                    if (s.charAt(j) != s.charAt(j - i)) {
                        match = false;
                        break;
                    }
                }
                if (match) {
                    return true;
                }
            }
        }
        return false;
    }


    //    无重复字符的最长子串
    public int lengthOfLongestSubstring(String s) {
        // 哈希集合，记录每个字符是否出现过
        Set<Character> occ = new HashSet<Character>();
        int n = s.length();
        // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
        int rk = -1, ans = 0;
        for (int i = 0; i < n; ++i) {
            if (i != 0) {
                // 左指针向右移动一格，移除一个字符
                occ.remove(s.charAt(i - 1));
            }
            while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
                // 不断地移动右指针
                occ.add(s.charAt(rk + 1));
                ++rk;
            }
            // 第 i 到 rk 个字符是一个极长的无重复字符子串
            ans = Math.max(ans, rk - i + 1);
        }
        return ans;
    }

    //    方法一：中心扩展法（推荐使用）
//    知识点：贪心思想
//    贪心思想属于动态规划思想中的一种，其基本原理是找出整体当中给的每个局部子结构的最优解，并且最终将所有的这些局部最优解结合起来形成整体上的一个最优解。
//    思路：
//    回文串，有着左右对称的特征，从首尾一起访问，遇到的元素都是相同的。但是我们这里正是要找最长的回文串，并不事先知道长度，怎么办？判断回文的过程是从首尾到中间，那我们找最长回文串可以逆着来，从中间延伸到首尾，这就是中心扩展法。
//    具体做法：
//    step 1：遍历字符串每个字符。
//    step 2：以每次遍历到的字符为中心（分奇数长度和偶数长度两种情况），不断向两边扩展。
//    step 3：如果两边都是相同的就是回文，不断扩大到最大长度即是以这个字符（或偶数两个）为中心的最长回文子串。
//    step 4：我们比较完每个字符为中心的最长回文子串，取最大值即可。
    public int fun(String s, int begin, int end) {
        //每个中心点开始扩展
        while (begin >= 0 && end < s.length() && s.charAt(begin) == s.charAt(end)) {
            begin--;
            end++;
        }
        //返回长度
        return end - begin - 1;
    }

    public int getLongestPalindrome(String A) {
        int maxlen = 1;
        //以每个点为中心
        for (int i = 0; i < A.length() - 1; i++)
            //分奇数长度和偶数长度向两边扩展
            maxlen = Math.max(maxlen, Math.max(fun(A, i, i), fun(A, i, i + 1)));
        return maxlen;
    }


    public void reverseString(char[] s) {
        int n = s.length;
        for (int left = 0, right = n - 1; left < right; ++left, --right) {
            char tmp = s[left];
            s[left] = s[right];
            s[right] = tmp;
        }
    }


    // 获取一个字符串在另一个字符串中出现的次数。
    public int times(String str1, String str2) {
        int maxLen = str1.length();
        int minLen = str2.length();
        int index = 0;
        int count = 0;
        if (minLen < maxLen) {
            while ((index = str1.indexOf(str2, index)) != -1) {
                count++;
                index += minLen;
            }
        }
        return count;
    }

 /*
    4.获取两个字符串中最大相同子串。比如：
str1 = "abcwerthelloyuiodef“;str2 = "cvhellobnm"
提示：将短的那个串进行长度依次递减的子串与较长的串比较。
     */

    public String getMaxSameString(String str1, String str2) {
        //利用三目运算判断出字符串的长短
        String maxStr = (str1.length() >= str2.length()) ? str1 : str2;
        String minStr = (str1.length() < str2.length()) ? str1 : str2;

        int minlength = minStr.length();//得到短字符串的长度
        for (int i = 0; i < minlength; i++) {
            for (int x = 0, y = minlength - i; y <= minlength; x++, y++) {//保证循环中截取的字符串长度一样
                String subStr = minStr.substring(x, y);//截取字符串长度
                if (maxStr.contains(subStr)) {//判断是否包含此字符串
                    return subStr;
                }
            }
        }
        return null;
    }


}
